package dataStructure.LinkList;


/*双向链表*/
public interface DoubleLinkedList {
    // 返回头节点
    DNode  getHead();
    // 头插法  逆序添加
    void addFirst(int data);

    // 尾插法 顺序添加
    void addLast(int data);

    // 任意位置插入，第一数据节点为0号下标
    boolean addIndex(int index, int data);

    // 查找是否包含关键字 key 在链表中
    boolean contains(int data);

    // 按值查询
    DNode searchNodeByData(int data);

    // 删除第一次出现的关键字为 key 的节点
    boolean remove(int data);

    // 删除所有值为 key 的节点
    void removeAllKey(int data);

    // 更新
    boolean updateNodeByIndex(int index,int data);

    // 得到链表的长度
    int size();

    // 打印链表
    void display();

    // 清空链表以防内存泄漏
    void clear();

    //获取最后一个节点
    DNode acquireLastNode();
    
    // 找最小节点
    DNode searchMinNode();

    // 根据索引找节点
    DNode searchNodeByIndex(int index);
}
class DLinkedList implements DoubleLinkedList{

    private DNode Dhead = new DNode(-1); // 默认头节点  带头节点的
    
    @Override
    public DNode getHead() {
        return Dhead;
    }

    @Override
    public void addFirst(int data) {
        // 因为head节点不能动，因此我们需要一个辅助遍历 temp
        DNode temp = this.Dhead;

        // 看看此时链表是否有节点
        if (size()>0){
            DNode node = new DNode(data);
            node.next = temp.next;
            temp.next.pre = node;
            temp.next = node;
            node.pre = temp;

        }else {
            // 没有节点作为第一个节点插入
            DNode node = new DNode(data);
            temp.next = node;
            node.pre = temp;
        }

    }

    @Override
    public void addLast(int data) {
        // 因为head节点不能动，因此我们需要一个辅助遍历 temp
        DNode temp = this.Dhead;

        // 遍历链表，找到最后
        while (temp.next!=null) {
            temp = temp.next;
        }
        // 当退出while循环时，temp就指向了链表的最后
        // 形成一个双向链表
        DNode node = new DNode(data);
        temp.next = node;
        node.pre = temp;
    }

    @Override
    public boolean addIndex(int index, int data) {
        // 空链表直接头插
        if(size()==0) {
            this.addFirst(data);
            return true;
        }

        if (size() == index){
            this.addLast(data);
            return true;
        }
        System.out.println("插入");
        DNode node = new DNode(data);
        DNode temp = searchNodeByIndex(index);

        if(temp !=null){
            node.next = temp.next;
            temp.next.pre = node;
            temp.next = node;
            node.pre = temp;
            return true ;
        }
        return false;
    }

    @Override
    public boolean contains(int data) {
        if(this.Dhead==null){
            return false;  //空链表直接返回false
        }

        DNode temp = this.Dhead;  //
        while (temp.next!=null) {
            if(temp.next.getData()==data){
                return true;
            }else {
                temp=temp.next;
            }


        }
        return false;//完成遍历后没有找到，返回false
    }

    /* 按值查询 并返回节点*/
    @Override
    public DNode searchNodeByData(int data) {
        if(this.size() ==0){
            return null;  //空链表直接返回null
        }

        DNode temp = this.Dhead;  //
        while (temp.next!=null) {
            if(temp.next.getData()==data){
                return temp.next;
            }else {
                temp=temp.next;
            }
        }
        return null;//完成遍历后没有找到，返回false
    }

    @Override
    public boolean remove(int data) {
        if(this.size() ==0){
            return false;  //空链表直接返回null
        }
        DNode temp = this.Dhead.next;  //
        while (temp!=null) {
            if(temp.getData()==data){
                // 可以删除
                temp.pre.next = temp.next;
                // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                    System.out.println("删除的不是最后一个节点");
                }else {
                    System.out.println("删除是最后一个节点");
                }
                return true;
            }else {
                temp=temp.next;
            }
        }
        System.out.println("无该节点!");
        return false;
    }

    @Override
    public void removeAllKey(int data) {

    }

    @Override
    public boolean updateNodeByIndex(int index, int data) {
//        System.out.println("this.size()"+this.size());
        if(index<0||index>this.size()){  //判断位置合法性
            System.out.println("index位置不合法");
            return false;
        }
        DNode node = searchNodeByIndex(index);
        if (node!=null){
            node.setData(data);
            return true ;
        }

        return false;
    }

    @Override
    public int size() {
        int count=0;
        DNode temp = this.Dhead;
        while (temp.next!=null) {//遍历链表，求出长度，返回长度 (不包含头节点)
            count++;
            temp=temp.next;
        }
        return count;
    }

    @Override
    public void display() {
        DNode temp=this.Dhead;
        if (temp.next ==null){
            System.out.println("双链表为空");
            return;
        }
        while (temp!=null) {//设置循环遍历链表 完成打印
            System.out.println(temp.toString()+" ");
            temp=temp.next;
        }
    }

    @Override
    public void clear() {
       this.Dhead = null;
    }

    @Override
    public DNode acquireLastNode() {
        if (size()==0){
            throw new RuntimeException("当前没有节点 获取最后一个节点失败");
        }
        DNode temp = this.Dhead;
        while (temp.next!=null){
            temp = temp.next;
        }
        return temp;
    }

    // 先封装一个方法用来找指定位置 的节点
    @Override
    public DNode searchNodeByIndex(int index) {  // 头结点索引是0 第一个元素索引是1
        if(index<0||index>this.size()){  //判断位置合法性
            throw new RuntimeException("index位置不合法");
        }
        if (index==0){
            return this.Dhead; // 头结点就是第一个节点
        }
        DNode temp = this.Dhead;
        int count = 0;
        while (count != index) { //找到指定位置的节点
            count++;
            temp=temp.next;
        }
        return temp;
    }

    @Override
    public  DNode searchMinNode (){
        if (size()==0){
            throw new RuntimeException("当前没有节点 获取前驱失败");
        }
        if (size()==1){
            return this.Dhead;
        }

//        System.out.println("Dhead"+this.Dhead);
        DNode minNodePre = this.Dhead;
        DNode minNode = this.Dhead.next;
        DNode pre =this.Dhead.next;
        DNode cur = this.Dhead.next.next;
        while (cur != null) {
            if (cur.getData() < minNode.getData()) {
                minNodePre = pre;
                minNode = cur;
            }
            pre = cur;
            cur = cur.next;
        }
        return minNode;
    }
}

class DNode{
    private int data;
    public DNode next;; //指向下一个节点
    public DNode pre;; //指向上一个节点
    //构造器
    public DNode(){

    }
    public DNode(int data){
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    //为了显示方法，我们重新toString
    @Override
    public String toString() {
        return "DNode [data=" + data +"]";
    }
}

class TestDLinkList{
    public static void main(String[] args) {

        DLinkedList dLinkedList = new DLinkedList();
        dLinkedList.addLast(2);
        dLinkedList.addLast(3);
        dLinkedList.addLast(4);
        dLinkedList.addFirst(5);
        dLinkedList.addFirst(6);
        dLinkedList.addFirst(1);
        dLinkedList.addIndex(2,50);
//        dLinkedList.updateNodeByIndex(2,500);
//        dLinkedList.remove(50);

        dLinkedList.display();
        System.out.println( dLinkedList.size());
        System.out.println("找最小的节点");
        System.out.println( dLinkedList.searchMinNode());
//        System.out.println( dLinkedList.searchNodeByIndex(2));
//        System.out.println( dLinkedList.acquireLastNode());
//        System.out.println( dLinkedList.contains(4));
//        System.out.println( dLinkedList.contains(40));


    }
}